Three-dimensional (“3D”) computer graphics are used in various 3D visualization and/or simulation tools. Volume graphics represent a promising way to achieve the degree of realism required for high quality 3D visualization and simulation applications because volume models can contain all the surface and internal characteristics of a real object. This is in contrast to surface-based graphics, such as polygonal graphics which utilize a plurality of flat surfaces called “polygons,” typically triangles, to represent the surfaces of a 3D object. As such, surface-based graphics contain only the information about the surfaces of a 3D object. In the case of volume graphics, on the other hand, volume elements (i.e., “voxels”) are the base data used to represent 3D objects.
Typically, voxels are simply pixels that have a third coordinate z in addition to x and y coordinates in a Cartesian coordinate system (though voxels may also take various other forms). In other words, voxels are equally sized cubes that form a discretely defined 3D space. A typical voxel-based 3D scene can consist of one or more “voxel sets,” each of which in turn consists of one or more voxels.
3D voxel data are rendered to produce a 2D image on a suitable output device, such as a video display or a printer. As used herein, the term “render” means to produce a 2D graphics image on an output device from a 3D voxel data file.
NGRAIN® graphics technology, embodied in various software available from NGRAIN Corp. of Vancouver, B.C., Canada, offers a volume-graphic based 3D visualization platform to build real time interactive 3D applications. Briefly, NGRAIN® technology permits 3D modeling of an object, wherein each of multiple parts or layers forming the object can be represented as a voxel set, consisting of one or more voxels. Thus, according to NGRAIN® technology, it is possible to manipulate each part or layer independently from each other or from the object as a whole, in 3D space, such as to create an exploded view of the object to show the details of its parts, or to peel off an outer layer of the object to reveal its inner layer. Since the voxel data structure used in NGRAIN® technology permits each voxel to be associated with an unlimited number of attributes (color, texture, normal, weight, density, etc.), these attributes can be used to give a rendered image a highly realistic look. Further, the voxel data structure and routines used to construct, manipulate, and render voxel data are such that specialized graphics hardware is not required—NGRAIN technology can run on any conventional personal computer, including a laptop.
Various details of NGRAIN® technology are described in commonly owned Patent Cooperation Treaty Publication No. WO 02/07088 A2 entitled “LIGHTING ADJUSTMENT METHODS AND APPARATUS FOR VOXEL DATA,” commonly owned Patent Cooperation Treaty Publication No. WO 02/07089 A2 entitled “APPARATUS AND METHOD FOR ASSOCIATING VOXEL INFORMATION WITH DISPLAY POSITIONS,” commonly owned U.S. Pat. No. 6,867,774 B1 entitled “METHOD AND APPARATUS FOR TRANSFORMING POLYGON DATA TO VOXEL DATA FOR GENERAL PURPOSE APPLICATIONS,” commonly owned U.S. Pat. No. 7,050,054 B2 entitled “METHOD, APPARATUS, SIGNALS AND CODES FOR ESTABLISHING AND USING A DATA STRUCTURE FOR STORING VOXEL INFORMATION,” commonly owned U.S. Pat. No. 7,218,323 B1 entitled “METHOD AND SYSTEM FOR RENDERING VOXEL DATA WHILE ADDRESSING MULTIPLE VOXEL SET INTERPENETRATION,” commonly owned U.S. Pat. No. 7,317,456 entitled “METHOD AND APPARATUS FOR TRANSFORMING POINT CLOUD DATA TO VOLUMETRIC DATA,” and commonly owned U.S. Pat. No. 7,317,456 entitled “METHOD AND SYSTEM FOR ORGANIZING AND RENDERING MULTIPLE GEOMETRIC PARTS WITHIN A VOLUME GRAPHICS DATA SET,” all of which are specifically incorporated herein by reference. Additional details of NGRAIN® technology can also be found in an article, “Myths and Truths of Interactive Volume Graphics,” a paper that has been published in I/ITSEC 2004 Conference.
FIG. 1 shows a simple example of a 4×4×4 voxel set 10 containing 64 possible geometric locations. Eight of these locations include occupied voxels 12a-12h, at [1,2,1], [2,2,1], [3,2,1], [2,2,2], [1,3,1], [2,3,1], [3,3,1], and [2,3,2], respectively, which collectively form a 3D object 14. The rest of the locations within the voxel set 10 are empty. Each voxel set may contain occupied voxels and/or empty voxels. Each voxel within the voxel set 10 is defined by its geometric location [x, y, z] in the Cartesian coordinate system. Each voxel is associated with a set of attributes, such as its shade information including color and alpha values, normal (vector), texture, part/layer number (i.e., to which voxel set it belongs), etc.
FIG. 2A shows an example of a polygon mesh object 16, which is formed of a plurality of triangle polygons 18. (Eight polygons are visible in FIG. 2A). Each polygon is defined by its vertices 20 in the 3D Cartesian coordinate system. Specifically, referring to FIG. 2B, each polygon is defined by its vertices 20, and each vertex 20 is typically associated with a set of attribute values such as a normal 21a, a color value 21b, and an intensity 21c. A normal is a unit vector that is perpendicular to a surface at a designated point, and is used during image rendering to apply appropriate lighting to an object being rendered. The normals are typically normalized, i.e., the magnitude of each normal is 1. Color or “RGB” (red, green, blue) values are usually 8-bit character values from which the range of colors that can be displayed by a rendering system are generated. Intensity refers to the brightness or darkness of an object at a particular point. As discussed above, the polygon mesh object 16 is hollow inside, and thus includes no information concerning the internal structure/characteristics of the object 16. Also, rendering of a high quality polygon mesh to approximate a curved surface usually consists of processing numerous polygons of various shapes and sizes, and thus is computationally intensive.
Despite these disadvantages, polygon mesh data are widely created and used today, as most 3D modeling software can generate polygon mesh data. These polygon mesh data in their present form, however, cannot be processed using NGRAIN® technology. To permit a user to enjoy the power of NGRAIN® technology, i.e., to achieve highly realistic and interactive visualization and simulation of 3D objects on a standard PC, the 3D objects that currently exist in polygon format need to be converted to voxels processable by NGRAIN® technology. U.S. Pat. No. 6,867,774 B1, incorporated by reference above, describes various methods and systems for converting polygon mesh data to voxels, including methods and systems for transferring any attribute data, such as color, intensity, and normal, from each polygon to the corresponding voxel(s). The present invention is directed to providing further methods and systems directed to calculating normals when converting polygon mesh data to voxel data.